package _2022.hot100._148_排序链表;

import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-05-05 15:32
 */

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val=x;
        next=null;
    }
}
public class Solution {
    public ListNode sortList(ListNode head){
        return sortList(head,null);
    }

    public ListNode sortList(ListNode head,ListNode tail){
        if(head==null){
            return head;
        }
        if(head.next==tail){
            head.next=null;
            return head;
        }
        ListNode slow=head,fast=head;
        while(fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if(fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        ListNode list1=sortList(head, mid);
        ListNode list2=sortList(mid,tail);
        ListNode sorted=merge(list1,list2);
        return sorted;
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode preHead=new ListNode(-1);
        ListNode tmp=preHead,tmp1=list1,tmp2=list2;
        while(tmp1!=null&&tmp2!=null){
            if(tmp1.val<=tmp2.val){
                tmp.next=tmp1;
                tmp1=tmp1.next;
            }else{
                tmp.next=tmp2;
                tmp2=tmp2.next;
            }
            tmp=tmp.next;
        }

        if(tmp1!=null){
            tmp.next=tmp1;
        }
        if(tmp2!=null){
            tmp.next=tmp2;
        }
        return preHead.next;
    }

}
